﻿#define _CRT_SECURE_NO_WARNINGS 1


#include<iostream>
#include<map>
using namespace std;


class Node {
public:
	int val;
	Node* next;
	Node* random;

	Node(int _val) {
		val = _val;
		next = NULL;
		random = NULL;
	}
};

class Solution {
public:
	Node* copyRandomList(Node* head) {
		map<Node*, Node*> nodeMap;
		Node* copyhead = nullptr, * copytail = nullptr;
		Node* cur = head;
		while (cur)
		{
			if (copytail == nullptr)
			{
				copyhead = copytail = new Node(cur->val);
			}
			else
			{
				copytail->next = new Node(cur->val);
				copytail = copytail->next;
			}
			// 原节点和拷⻉节点map kv存储
			nodeMap[cur] = copytail;
			cur = cur->next;
		}
		// 处理random
		cur = head;
		Node* copy = copyhead;
		while (cur)
		{
			if (cur->random == nullptr)
			{
				copy->random = nullptr;
			}
			else
			{
				copy->random = nodeMap[cur->random];
			}
			cur = cur->next; 
			copy = copy->next;
		}
		return copyhead;
	}
};




int main()
{
	Node a = Node(2);
	Node b = Node(3);
	Node c = Node(4);
	Node d = Node(5);
	Node e = Node(6);
	Node f = Node(7);
	Node g = Node(8);
	a.next = &b;
	b.next = &c;
	c.next = &d;
	d.next = &e;
	e.next = &f;
	f.next = &g;
	g.next = nullptr;
	a.random = &b;
	b.random = &d;
	c.random = &e;
	d.random = &a;
	e.random = &f;
	f.random = nullptr;
	g.random = &c;

	Solution  jj;
	Node* ll = jj.copyRandomList(&a);

	return 0;
}